import java.util.ArrayList;
import java.util.Iterator;
import java.util.Stack;

public class ListTable {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode node=head;
        ListNode pre=head;
        int num=0;
        while (pre!=null){
            pre= pre.next;
            num++;
        }
        if(num==n) return head.next;
        num=num-n-1;
        int numTemp=0;
        while (num!=numTemp){
            numTemp++;
            node=node.next;
        }
        node.next=node.next.next;
        return head;
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ArrayList<Integer> result=new ArrayList<>();
        int a1;
        int a2;
        while (l1!=null||l2!=null){
            if(l1==null){
                a1=Integer.MAX_VALUE;
                a2=l2.val;
            }else if(l2==null){
                a2=Integer.MAX_VALUE;
                a1=l1.val;
            }else {
                a1=l1.val;
                a2=l2.val;
            }
            if(a1<=a2){
                result.add(a1);
                if(l1!=null){
                    l1=l1.next;
                }
            }else {
                result.add(a2);
                if(l2!=null){
                    l2=l2.next;
                }
            }
        }
        Iterator<Integer> iterator=result.iterator();
        if(iterator.hasNext()){
            ListNode node=new ListNode(iterator.next());
            ListNode res=node;
            while (iterator.hasNext()){
                node.next=new ListNode(iterator.next());
                node=node.next;
            }
            return res;
        }else {
            return null;
        }
    }

    public ListNode reverseList(ListNode head) {
        ListNode node=head;
        if(node==null)return null;
        int len=1;
        while (node.next!=null){
            node=node.next;
            len++;
        }
        ListNode result=node;
        ListNode temp=result;
        for (int i=1;i<len;i++){
            node=head;
            for (int j=0;j<len-i-1;j++){
                node=node.next;
            }
            temp.next=new ListNode(node.val);
            temp=temp.next;
        }
        return result;
    }
//    ListNode newHead = null;
//    void dfs(ListNode p1, ListNode p2) {
//        if (p2 == null) {
//            newHead = p1;
//            return;
//        }
//        ListNode tmp = p2.next;
//        p2.next = p1;
//
//        dfs(p2, tmp);
//
//    }
//    public ListNode reverseList(ListNode head) {
//        ListNode result=head;
//        if (result == null ||result.next == null) return result;
//        dfs(result, result.next);
//        result.next = null;
//        return newHead;
//    }

    public void deleteNode(ListNode node,int n) {
        ListNode result=node;
        if(node.val==n){
            node=node.next;
        }
        while (result.next!=null&&result.next.val!=n){
            result=result.next;
        }
        result.next=result.next.next;
    }

    public boolean hasCycle(ListNode head) {
        ListNode first=head;
        ListNode second=head;
        if(second.next==null||second.next.next==null)return false;
        else {
            try {
                first=first.next;
                second=second.next.next;
                while (first!=second){
                    first=first.next;
                    second=second.next.next;
                }
                return true;
            }catch (Exception e){
                return false;
            }
        }
    }

    public boolean isPalindrome(ListNode head) {
        if (head==null|| head.next==null) return true;
        ListNode slow = head, fast = head;
        Stack<Integer> s=new Stack<>();
        s.push(head.val);
        while (fast.next!=null && fast.next.next!=null) {
            slow = slow.next;
            fast = fast.next.next;
            s.push(slow.val);
        }
        if (fast.next==null) s.pop();
        while (slow.next!=null) {
            slow = slow.next;
            int tmp = s.peek(); s.pop();
            if (tmp != slow.val) return false;
        }
        return true;
    }
}
